package com.mlh.backtracking;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @author 缪林辉
 * @date 2024/4/6 12:26
 * @DESCRIPTION
 */

// 给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的 子集
// 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
// 输入：nums = [1,2,3]
// 输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
public class 子集 {
    // 通常都是叶子节点作为一个结果集，但这里不是，这里任何一层树节点都是结果集
    // 这种问题被称为子集问题，那么组合问题和分割问题都是收集树的叶子节点，而子集问题是找树的所有节点！
    // 求取子集问题，不需要任何剪枝！因为子集就是要遍历整棵树。
    //子集问题通过遍历自己后面的节点来防止元素重复
    LinkedList<Integer> path=new LinkedList<>();//路径
    List<List<Integer>> res=new ArrayList<>();//最终结果
    public List<List<Integer>> method1(int[] nums) {
        recursion(0,nums);
        res.add(new ArrayList<>());
        return res;
    }
    public void recursion(int head,int[]nums){
        if (head>=nums.length){
            return;
        }
        for (int i = head; i <nums.length ; i++) {
            path.add(nums[i]);
            res.add(new ArrayList<>(path));
            recursion(i+1,nums);
            path.removeLast();
        }
    }
    public List<List<Integer>> practice(int[] nums) {
         res.add(new ArrayList<>());
        recursionPractice(0,nums);
        return res;
    }

    private void recursionPractice(int index, int[] nums) {
        if(index>=nums.length){
            return;
        }
        for (int i = index; i <nums.length ; i++) {
            path.add(nums[i]);
            res.add(new ArrayList<>(path));
            recursionPractice(i+1,nums);
            path.removeLast();
        }
    }

    public List<List<Integer>> practice2(int[] nums) {
        res.add(new ArrayList<>());
        if(nums.length==0){
            return res;
        }
        recursionPractice2(nums,0);
        return res;
    }

    public void recursionPractice2(int[]nums,int startIndex){
        for (int i = startIndex; i < nums.length; i++) {
            path.add(nums[i]);
            res.add(new ArrayList<>(path));
            recursionPractice2(nums,i+1);
            path.removeLast();
        }
    }
}
